Aufgabe: Die Übergangstabelle eines DEA siehe wie folgt aus:

\begin{matrix}| & 0 & 1 \\ → q_{1} & q_{2} & q_{1} \\ q_{2} & q_{3} & q_{3} \\ ^{∗}q_{3} & q_{3} & q_{2} \end{matrix}

Die Graph eines DEA sehe wie folgt aus:

q_{1}  q_{2}  q_{3} 0 1  0 1 1  0

a) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(0)}. Hinweis: Stellen Sie sich den Zustand q_{i} so vor, als handle es sich um den Zustand mit der ganzzahligen Nummer i.

b) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(1)}. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.

c) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(2)}. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.

d) Formulieren Sie einen regulären Ausdruck für die Sprache des Automaten.

e) Konstruieren Sie das Übergangsdiagramm für den DEA, und geben sie einen regulären Ausdruck für die Sprache des Automaten an, indem sie q_{2} eleminieren.

Lösung:

a) Wir müssen alle R_{ij}^{(0)} für alle i, j ∈ {1, 2, 3} bestimmen. Anders ausgedrückt: Wie kommt man von Zustand i zu Zustand j ohne über einen Zustand zu gehen, der höher als 0 ist. Da die Nummerierung der Zustände bei 1 beginnt, bedeutet das nichts anderes als: Wie komme ich von Zustand i ohne Umweg zu Zustand j. Dies führt zu folgenden 9 zu berechnenden R_{ij}^{(0)}:

a) R_{11}^{(0)} = ε + 1 Von Zustand 1 nach Zustand 1 über keinen höheren Zustand als 0 gibt es 2 mögliche Pfade. Keine Eingabe (ε), oder Eingabe von 1.

b) R_{12}^{(0)} = 0 Von Zustand 1 nach Zustand 2 über keinen höheren Zustand als 0 gibt es genau einen möglichen Pfad. Die Eingabe von 0. c) R_{13}^{(0)} = ∅

Von Zustand 1 nach Zustand 3 über keinen höheren Zustand als 0 gibt es keinen Pfad → ∅. Dies ist der erste für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.

d) R_{21}^{(0)} = 1 Vom Zustand 2 nach Zustand 1 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit 1 beschriftet.

e) R_{22}^{(0)} = ε Vom Zustand 2 zu sich selbst über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit ε beschriftet.

f) R_{23}^{(0)} = 0 Vom Zustand 2 zum Zustand 3 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit 0 beschriftet

g) R_{31}^{(0)} = ∅ Vom Zustand 3 zum Zustand 1 über keinen höheren Zustand als 0 gibt es keinen Pfad → ∅.

h) R_{32}^{(0)} = 1 Vom Zustand 3 zum Zustand 2 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit 1 beschriftet.

i) R_{33}^{(0)} = ε + 0 Vom Zustand 3 zu sich selbst über keinen Pfad höher als 0 gibt es zwei Pfade, die Eingabe von ε oder 0.

b) Für die Berechnung aller R_{ij}^{(1)} muss nur noch die folgende Formel angewendet werden: R_{ij}^{(k)} = R_{ij}^{(k−1)} + R_{ik}^{(k−1)}(R_{kk}^{(k−1)})^{∗}R_{kj}^{(k−1)}

In diesem Fall ist k = 1 was zu k − 1 = 0 führt. Und diese R_{ij}^{(0)} wurden alle in a) schon gebildet. Folglich können die folgenden 9 R_{ij}^{(k)} leicht gebildet werden und müssen dann nur noch richtig vereinfacht werden. Vereinfacht wird nach den Regeln:

• (ε + R)^{∗} = R^{∗}

• (ε + 1)1^{∗} = 1^{∗}

• ∅R = R∅ = ∅

• ∅ + R = R + ∅ = R

a) R_{11}^{(1)}= R_{11}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{11}^{(1−1)}

= (ε + 1) + (ε + 1)(ε + 1)^{∗}(ε + 1)

= (ε + 1) + (ε + 1)^{∗}

= (ε + 1)^{∗}

= 1^{∗}

b) R_{12}^{(1)}= R_{12}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= 0 + (ε + 1)(ε + 1)^{∗}0 = 0 + 1^{∗}0 = 1^{∗}0

c) R_{13}^{(1)}= R_{13}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= ∅ + (ε + 1)(ε + 1)^{∗}∅ = ∅ + ∅ = ∅

Dies ist der zweite für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.

d) R_{21}^{(1)}= R_{21}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{11}^{(1−1)}

= 1 + 1(ε + 1)^{∗}(ε + 1)) = 1 + 11^{∗} = 11^{∗}

e) R_{22}^{(1)}= R_{22}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= ε + 1(ε + 1)^{∗}0 = ε + 11^{∗}0

f) R_{23}^{(1)}= R_{23}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= 0 + 1(ε + 1)^{∗}∅ = 0

g) R_{31}^{(1)}= R_{31}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= ∅ + ∅(ε + 1)^{∗}∅ = ∅

h) R_{32}^{(1)}= R_{32}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= 1 + ∅(ε + 1)^{∗}0 = 1

i) R_{33}^{(1)}= R_{33}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= (ε + 0) + ∅(ε + 1)^{∗}∅ = ε + 0

c)Für die Berechnung aller R_{ij}^{(2)} muss wieder die Formel angewendet werden, nur ist k statt 1 diesmal 2 R_{ij}^{(k)} = R_{ij}^{(k−1)} + R_{ik}^{(k−1)}(R_{kk}^{(k−1)})^{∗}R_{kj}^{(k−1)}

a) R_{11}^{(2)}= R_{11}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})^{∗}R_{21}^{(1)}

= 1^{∗} + 1^{∗}0(ε + 11^{∗}0)^{∗}11^{∗} = 1^{∗} + 1^{∗}0(11^{∗}0)^{∗}11^{∗}

b) R_{12}^{(2)}= R_{12}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})^{∗}R_{22}^{(1)}

= 1^{∗}0 + 1^{∗}0(ε + 11^{∗}0)^{∗}(ε + 11^{∗}0) = 1^{∗}0(ε + 11^{∗}0)^{∗} = 1^{∗}0(11^{∗}0)^{∗}

c) R_{13}^{(2)}= R_{13}^{(1)} + R_{12}^{(1)}(R_{22}^{(1)})^{∗}R_{23}^{(1)}

= ∅ + 1^{∗}0(ε + 11^{∗}0)^{∗}0 = 1^{∗}0(11^{∗}0)^{∗}0

Dies ist der dritte für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.

d) R_{21}^{(2)}= R_{21}^{(1)} + R_{22}^{(1)}(R_{22}^{(1)})^{∗}R_{21}^{(1)}

= 11^{∗} + (ε + 11^{∗}0)(ε + 11^{∗}0)^{∗}11^{∗} = (11^{∗}0)^{∗}11^{∗}

e) R_{22}^{(2)}= R_{22}^{(1)} + R_{22}^{(1)}(R_{22}^{(1)})^{∗}R_{22}^{(1)}

= (ε + 11^{∗}0) + (ε + 11^{∗}0)(ε + 11^{∗}0)^{∗}(ε + 11^{∗}0) = (ε + 11^{∗}0)^{∗} = (11^{∗}0)^{∗}

f) R_{23}^{(2)}= R_{23}^{(1)} + R_{22}^{(1)}(R_{22}^{(1)})^{∗}R_{23}^{(1)}

= 0 + (ε + 11^{∗}0)(ε + 11^{∗}0)^{∗}0 = 0 + (11^{∗}0)^{∗}0 = (11^{∗}0)^{∗}0

g) R_{31}^{(2)}= R_{31}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})^{∗}R_{21}^{(1)}

= ∅ + 1(ε + 11^{∗}0)^{∗}11^{∗} = 1(ε + 11^{∗}0)^{∗}11^{∗} = 1(11^{∗}0)^{∗}11^{∗}

h) R_{32}^{(2)}= R_{32}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})^{∗}R_{22}^{(1)}

= 1 + 1(ε + 11^{∗}0)^{∗}(ε + 11^{∗}0) = 1(11^{∗}0)^{∗}

i) R_{33}^{(2)}= R_{33}^{(1)} + R_{32}^{(1)}(R_{22}^{(1)})^{∗}R_{23}^{(1)}

= (ε + 0) + 1(ε + 11^{∗}0)^{∗}0 = ε + 0 + 1(11^{∗}0)^{∗}0)

d) Um den Ausdruck zu formulieren, der die selbe Sprache beschreibt, wieder DEA, müssen alle Teilausdrücke R_{ij}^{(3)} für alle i ∈ q_{0} und j ∈ F (alle Ausdrücke die vom Startzustand zu einem akzeptierenden Zustand führen) vereinigt werden. Das betrifft bei diesem DEA nur jenen Ausdruck, der von Zustand 1(q_{0}) zu Zustand 3 (q_{2}) führt. Genauer:

R_{DEA} = R_{13}^{(3)}

Also muss noch der Ausdruck R_{13}^{(3)} gebildet werden:

R_{13}^{(3)}= R_{13}^{(2)} + R_{13}^{(2)}(R_{33}^{(2)})^{∗}R_{33}^{(2)} = (1^{∗}0(11^{∗}0)^{∗}0) + (1^{∗}0(11^{∗}0)^{∗})((11^{∗}0)^{∗})^{∗}(11^{∗}0)^{∗}0

= (1^{∗}0(11^{∗}0)^{∗}0) + (1^{∗}0(11^{∗}0)^{∗})(11^{∗}0)^{∗}(11^{∗}0)^{∗}0
= (1^{∗}0(11^{∗}0)^{∗}0) + (1^{∗}0(11^{∗}0)^{∗})(11^{∗}0)^{∗}0
= 1^{∗}0(11^{∗}0)^{∗}0 + 1^{∗}0(11^{∗}0)^{∗}(11^{∗}0)^{∗}0
= 1^{∗}0(11^{∗}0)^{∗}0

e)^{q_{1}  q_{2}  q_{3} 0 1  0 1 1  0}

Auf den Übergangspfeilen des DEAs stehen im Moment noch Zeichenreihen. Diese werden als erstes in reguläre Ausdrücke umgeschrieben. Danach sieht der DEA mit regulären Ausdrücken auf den Pfeilen wie folgt aus reguläre Ausdrücke seien hier mal fett gedruckt:

q_{1}  q_{2}  q_{3} 0 1  0 1 1  0

Man beachte, dass der reguläre Ausdruck, der die Zeichenkette bestehend aus {a} beschreibt, a lautet. Deshalb hat sich am Graphen selbst nichts geändert. Um nun den Zustand q_{2} zu eliminieren werden wie im Buch beschrieben, die r. Audrücke die zum Zustand q_{2} führen (seien a), die vom Zustand q_{2} zu sich selbst führen (seien b) und die, die vom Zustand weg führen (seien c) aneinander gereiht, in der Form abc. Da es noch Pfade gibt, die genau in die andere Richtung verlaufen, muss das ganze auch von q_{3} nach q_{1} in der Gegenrichtung gemacht werden. Weiter hin muss man beachten, dass ein Pfad jeweils von q_{1} über q_{2} zurück zu q_{1} und einer von q_{3} über q_{2} zurück zu q_{3} führt, mit den jewiligen Pfaden des Zustands zu sich selbst vereinigt werden. Dies führt zu dem folgenden Übergangsgraphen:

q_{1}  q_{3} 00 11 1 + 01  0 + 10
(1 + 01)^{∗}00((0 + 10) + (11(1 + 01)^{∗}00))^{∗}

Erklärung: Sind wir in q_{1}, kann beliebig oft (auch 0 mal) (1 + 01) in der Zeichenreihe kommen, das bewirkt keine Zustandsänderung. Deshalb ist der erste Teil (1 + 01)^{∗}. Um eine Zustandsänderung zu bewirken muss ein 00 kommen, um in q_{3} zu gelangen. deshalb wir dem ersten Teilausdruck ein 00 angehängt, was zu (1 + 01)^{∗}00 führt. In q_{3} sind wir im akzeptierenden Zustand. Jetzt kann beliebig oft (auch 0 mal) entweder (0 + 10) in der Zeichenreihe kommen(was den Zustand nicht verändert - der Automat bleibt in q_{3}), oder 11 (führt von q_{3} zu q_{1}), gefolgt von beliebig oft (1 + 01), gefolgt von 00 - das ergibt den Teilausdruck, der von q_{3} über q_{1} zurück zu q_{3} führt, womit wir wieder im akzeptierenden Zustand wären. Dieser Teilausdruck lautet also (11(1 + 01)^{∗}00). Da beliebig oft von q_{3} über q_{1} wieder zu q_{3} gewechselt werden darf wird dem ganzen noch ein Sternchen angehängt: (11(1 + 01)^{∗}00)^{∗}.

Jetzt weden einfach die beiden Teilausdrücke (1. der, der von q_{1} zu q_{3}; 2. der von q_{3} über q_{1} zuück zu q_{3}) aneinander gehängt, was den fertigen Ausdruck ergibt:

(1 + 01)^{∗}00((0 + 10) + (11(1 + 01)^{∗}00))^{∗}  (1)